#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool check[6][6];
    bool exist(vector<vector<char>>& board, string word)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == word[0])
                {
                    check[i][j] = true;
                    if (dfs(board, i, j, word, 1) == true)
                    {

                        return true;
                    }
                    else
                    {
                        check[i][j] = false;
                        continue;
                    }
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, int i, int j, string word, int pos)
    {
        if (pos == word.size())return true;
        if (i + 1 < board.size() && check[i + 1][j] == false && board[i + 1][j] == word[pos])
        {
            check[i + 1][j] = true;
            if (dfs(board, i + 1, j, word, pos + 1))return true;
            check[i + 1][j] = false;
        }
        if (i - 1 >= 0 && check[i - 1][j] == false && board[i - 1][j] == word[pos])
        {
            check[i - 1][j] = true;
            if (dfs(board, i - 1, j, word, pos + 1))return true;
            check[i - 1][j] = false;
        }
        if (j + 1 < board[0].size() && check[i][j + 1] == false && board[i][j + 1] == word[pos])
        {
            check[i][j + 1] = true;
            if (dfs(board, i, j + 1, word, pos + 1)) return true;
            check[i][j + 1] = false;
        }
        if (j - 1 >= 0 && check[i][j - 1] == false && board[i][j - 1] == word[pos])
        {
            check[i][j - 1] = true;
            if (dfs(board, i, j - 1, word, pos + 1)) return true;
            check[i][j - 1] = false;
        }
        return false;
    }
};